package syf.search;

import java.util.Arrays;

public class FibonacciSearch {
    public static int maxSize=20;
    public static void main(String[] args) {
        int[] arr={1,8,10,89,1000,1234};
        fibonacci1();

        System.out.println( fibonacciSearch(arr,1234));
//        int[] arr1=new int[maxSize];
//        arr1[0]=1;
//        arr1[1]=1;
//        fibonacci2(arr1,2);
    }

    /**
     *
     * @param arr 被查找的数组
     * @param val 需要查找的值
     * @return 返回对应的下标，默认为-1
     */
    public static int fibonacciSearch(int[] arr,int val){
        int low=0;
        int high=arr.length-1;
        int k=0;//表示斐波那契分割数值的下标
        int mid;//存放中间值下标
        int[] f=fibonacci1();//获取斐波那契数列
        //获取到斐波那契分割数值的下标
        while (high>f[k]-1){
            k++;
        }//因为f[k]的长度可能大于a的长度，因此我们需要使用Arrays类，构造一个新的数组，并指向arr[]
        //不足的部分会采用0填充
        int[] tmp=Arrays.copyOf(arr,f[k]);
        //对新的数组进行填充，用arr数组的最后一位  {1,8,10,89,1000,1234,1234,1234}
        for (int i=high+1;i<tmp.length;i++){
            tmp[i]=arr[high];
        }
        //使用while循环来处理，查找我们的数key
        while (low<=high){
            mid=low+f[k-1]-1;
            if (val<tmp[mid]){//我们应该继续向数组的前面查找（左）
                high=mid-1;
                //全部元素等于前面的元素+后面的元素 f[k]=f[k-1]+f[k-2];
                //因为前面有f[k-1]个元素，所以可以继续拆分 f[k-1]=f[k-2]+f[k-3]
                //即在f[k-1]的前面继续查找 k--
                k--;
            } else if (val>tmp[mid]) {
                low=mid+1;
                //因为前面有f[k-1]个元素，所以可以继续拆分 f[k-1]=f[k-2]+f[k-3]
                //f[k-1]=f[k-2]+f[k-3]
                //因为我们后面有f[k-2]个数，所以可以继续拆分f[k-2]=f[k-3]+f[k-4]
                //即在f[k-2]的前面进行查找k-=2
                k-=2;
            }else {
                //需要确定返回的high 还是 mid
                if (mid<=high) return mid;
                else return high;
            }
        }
            return -1;
    }

    /**
     * 构建斐波那契数列,使用非递归方式
     * @return 斐波那契数列
     * 后面的mid中 mid=F(k-1)-1，需要用到斐波那契数列，因此我们要先取得一个斐波那契数列
     */
    public static int[] fibonacci1(){
        int[] f=new int[maxSize];
        f[0]=1;
        f[1]=1;
        for (int i=2;i<maxSize;i++){
            f[i]=f[i-1]+f[i-2];
        }
        System.out.println(Arrays.toString(f));
        return f;
    }
    /**
     * 构建斐波那契数列,使用递归方式
     */
    public static void fibonacci2(int[] f, int index){
        if (index<maxSize){
            f[index]=f[index-2]+f[index-1];
            fibonacci2(f,(++index));
        }else {
            System.out.println(Arrays.toString(f));
        }
    }
}
